import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/17 9:28
 * @description 滑动窗口 + 单调队列
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {84, -37, 32, 40, 95};
        solution.shortestSubarray(nums, 167);
    }

    public int shortestSubarray(int[] A, int K) {
        int n = A.length;
        long[] preSum = new long[n + 1];
        for (int i = 0; i < A.length; i++) {
            preSum[i + 1] = preSum[i] + A[i];
            if (A[i] >= K) {
                return 1;
            }
        }
        int res = Integer.MAX_VALUE;
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n + 1; i++) {
            // 滑动窗口并不是单调增的，因为存在负数。
            while (!queue.isEmpty() && preSum[i] <= preSum[queue.getLast()]) {
                queue.removeLast();
            }
            while (!queue.isEmpty() && preSum[i] - preSum[queue.peek()] >= K) {
                res = Math.min(res, i - queue.poll());
            }
            queue.add(i);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}
